package DataStructures;

/**
 * 前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。前缀树至少支持这几种操作，即插入字符串、删除字符串，以及查找是否存在以某子串开头
 * 的字符串。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
 * 考虑一棵存储小写字母组成的单词的前缀树。前缀树将“分支”存储于边上，“单词”存储于结点上。每个结点上的单词就是从根到该结点走过的路径上的字母串成的。由
 * 于在到达根结点前没有经过任何边，因此根结点表示空字符串。
 */
public class Trie {
    class TrieNode {
        boolean isWord; // 是否存在以该结点结束的单词
        TrieNode[] children;

        public TrieNode(int nChildren) {
            children = new TrieNode[nChildren];
        }
    }

    private static final int N_CHILDREN = 26;
    TrieNode root;

    public Trie() {
        root = new TrieNode(N_CHILDREN);
    }

    public void insert(String word) {
        TrieNode ptr = root;
        char[] charArray = word.toCharArray();
        for (char ch : charArray) {
            if (ptr.children[ch - 'a'] == null) {
                ptr.children[ch - 'a'] = new TrieNode(N_CHILDREN);
            }
            ptr = ptr.children[ch - 'a'];
        }
        ptr.isWord = true;
    }

    public boolean search(String word) {
        TrieNode ptr = root;
        char[] charArray = word.toCharArray();
        for (char ch : charArray) {
            if (ptr.children[ch - 'a'] == null) return false;
            ptr = ptr.children[ch - 'a'];
        }
        return ptr.isWord;
    }

    /**
     * 查找是否存在以prefix为前缀的单词
     */
    public boolean startsWith(String prefix) {
        TrieNode ptr = root;
        char[] charArray = prefix.toCharArray();
        for (char ch : charArray) {
            if (ptr.children[ch - 'a'] == null) return false;
            ptr = ptr.children[ch - 'a'];
        }
        return true;
    }
}
